import time

class Sort():
    
    def __init__(self, data, sorted=None):
        self.data = data
        self.sorted = sorted

    def __len__(self):
        return len(self.data)
    
    def __str__(self):
        data = "data:\n" + str(self.data)
        sorted = "sorted:\n" + str(self.sorted)
        return data + '\n' + sorted

    def calcTime(func):
        '''
        函数修饰器, 用来计算各个排序算法的执行时间
        最终返回一个 list [temp, time_sum]
                        temp : 排序结果
                        time_sum : 执行时间(单位ms)
        '''
        def warpper (self):
            time_start = time.perf_counter()
            temp = func(self)
            time_end = time.perf_counter()
            time_sum = time_end - time_start
            return [temp, time_sum*1000]
        return warpper

    @calcTime
    def InS(self):
        '''
        插入排序
        '''
        data = [i for i in self.data]
        for i in range(1, len(data)):
            j = i
            while j-1 >= 0 and data[j-1] > data[j]:
                data[j], data[j-1] = data[j-1], data[j]
                j -= 1
        return data
    
    @calcTime
    def ShellS(self):
        '''
        希尔排序
        '''
        data = [i for i in self.data]
        d = len(data) // 2
        while d >= 1:
            for i in range(d, len(data)):
                j = i-d
                while j >= 0 and data[j+d] < data[j]:
                    data[j+d], data[j] = data[j], data[j+d]
                    j -= d
            d = d // 2
        return data  

    @calcTime
    def BubbleS(self):
        '''
        冒泡排序
        '''
        data = [i for i in self.data]
        exchange = len(data) - 1
        while exchange != 0:
            bound, exchange = exchange, 0
            for i in range(bound):
                if data[i] > data[i+1]:
                    data[i], data[i+1] = data[i+1], data[i]
                    exchange = i
        return data

    @calcTime
    def QuickS(self):
        '''
        快速排序
        '''
        data = [i for i in self.data]
        def Partition(first, last):
            '''
            一次划分
            '''
            i, j = first, last
            while i < j :
                while i < j and data[i] <= data[j]: j -= 1
                if i < j:
                    data[i], data[j] = data[j], data[i]
                    i += 1
                while i < j and data[i] <= data[j]: i += 1
                if i < j:
                    data[i], data[j] = data[j], data[i]
                    j -= 1
            return i

        def Quick(first=0, last=len(data)-1):
            if first >= last: return
            else:
                pivot = Partition(first, last)
                Quick(first, pivot-1)
                Quick(pivot+1, last)

        Quick(0, len(data)-1)
        return data

    @calcTime
    def HeapS(self):
        '''
        堆排序
        '''
        data = [i for i in self.data]
        def siftdown(data, e, begin, end):
            i, j = begin, begin * 2 + 1
            while j < end:
                if j + 1 < end and data[j] > data[j + 1]:
                    j += 1
                if e < data[j]:
                    break
                data[i] = data[j]
                i, j = j, j * 2 + 1
            data[i] = e

        end = len(data)
        for i in range(end // 2 - 1, -1, -1):
            siftdown(data, data[i], i, end)
        for i in range((end - 1), 0, -1):
            e = data[i]
            data[i] = data[0]
            siftdown(data, e, 0, i)
            """
            利用小根堆，故利用切片操作逆序输出
            """
        data = data[::-1]
        
        return data
    
    @calcTime
    def MergeS(self):
        '''
        二路归并排序的非递归实现
        '''
        data = [i for i in self.data]
        def Merge(first1, last1, last2):
            '''
            合并两个序列: first1 --> last1
                         last1+1 --> last2
            '''
            temp = []
            i, j = first1, last1+1
            while i <= last1 and j <= last2:
                if data[i] <= data[j]: 
                    temp.append(data[i])
                    i += 1
                else:
                    temp.append(data[j])
                    j += 1
            while i <= last1:
                temp.append(data[i])
                i += 1
            while j <= last2:
                temp.append(data[j])
                j += 1
            data[first1:last2+1] = temp
            del temp
        
        def MergePass(h):
            i = 0
            while i+2 * h <= len(data):
                # 有两个长度为 h 的子序列
                Merge(i, i+h-1, i+2*h-1)
                i = i + 2 * h
            if i + h < len(data):
                # 两个子序列其中一个小于 h
                Merge(i, i+h-1, len(data)-1)

        h = 1   # 从每个子序列长度为 1 开始
        while h < len(data):
            MergePass(h)
            h = 2 * h
        
        return data


if __name__ == '__main__':
    a = Sort([59, 20, 17, 36, 98, 14, 23, 83, 13, 28])
    print(a.QuickS())
